//https://leetcode.cn/problems/find-median-from-data-stream/

class MedianFinder {
    priority_queue<int> left;
    priority_queue<int, vector<int>, greater<int>> right;
public:
    MedianFinder() {

    }

    void addNum(int num) {
        if (left.size() == right.size())
        {
            if (left.size() == 0 || num <= left.top())
            {
                left.push(num);
            }
            else
            {
                right.push(num);
                int top = right.top();
                left.push(top);
                right.pop();
            }
        }
        else
        {
            if (num <= left.top())
            {
                left.push(num);
                int top = left.top();
                right.push(top);
                left.pop();
            }
            else
            {
                right.push(num);
            }
        }

    }

    double findMedian() {
        if (left.size() == right.size())
            return (left.top() + right.top()) / 2.0;

        return left.top();

    }
};